import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
    //JZ54 二叉搜索树的第k个节点
    //，请找出其中的第 k 小的TreeNode结点值
    public int KthNode (TreeNode proot, int k) {
        //找一个顺序表保存起来
        List<TreeNode> list1 = new ArrayList<>();
        proder(proot, list1);
        //把k个节点保存起来
        int len = list1.size();
        PriorityQueue<TreeNode> p1 = new PriorityQueue<>(new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return o2.val - o1.val;
            }
        });
        for (int i = 0; i < len; i++) {
            if (i < k) {
                p1.offer(list1.get(i));
            }//建成大堆
            else {
                TreeNode cur = p1.peek();
                if (cur.val > list1.get(i).val) {
                    p1.poll();
                    p1.offer(list1.get(i));
                }
            }
        }
        return p1.poll().val;
    }
    private static  void proder(TreeNode root,List<TreeNode>list1){
        if(root==null){
            return;
        }
        list1.add(root);
        proder(root.left,list1);
        proder(root.right,list1);
    }
    //JZ8 二叉树的下一个结点
    class TreeLinkNode{
        int val;
        TreeLinkNode left;
        TreeLinkNode right;
        TreeLinkNode next;

        public TreeLinkNode(int val) {
            this.val = val;
        }
    }
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //先找到根节点
        TreeLinkNode cur=pNode;
        while(cur.next!=null){
            cur=cur.next;
        }//此时cur是根节点
        List<TreeLinkNode> list=new ArrayList<>();
        //中序遍历
       inorder(cur,list);
       int size=list.size();
        for (int i = 0; i <size-1 ; i++) {
            if(list.get(i)==pNode){
                return list.get(i+1);
            }
        }
        return null;
    }
    private static  void inorder(TreeLinkNode root,List<TreeLinkNode>list){
        if(root==null){
            return;
        }
        inorder(root.left,list);
        list.add(root);
        inorder(root.right,list);
    }
    //对称二叉树
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }
    public  static TreeNode root;

    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }//子问题
        return isSymmetricalChild(pRoot.left, pRoot.right);
    }

    protected static boolean isSymmetricalChild(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 != null ||
                r1 != null && r2 == null) {
            return false;
        } else if (r1 == null && r2 == null) {
            return true;
        } else {
            if (r1.val != r2.val) {
                return false;
            }
        }
        return isSymmetricalChild(r1.left, r2.right)
                && isSymmetricalChild(r1.right, r2.left);
    }
}
